home *** CD-ROM | disk | FTP | other *** search
/ EuroCD 3 / EuroCD 3.iso / Programming / vbcc / loop.c < prev    next >
C/C++ Source or Header  |  1998-06-24  |  61KB  |  1,565 lines
  1. /*  $VER: vbcc (loop.c) V0.4     */
  2. /*  schleifenorientierte Optimierungen  */
  3.  
  4. #include "opt.h"
  5.  
  6. static char FILE_[]=__FILE__;
  7.  
  8. #define MOVE_IC 1
  9. #define MOVE_COMP 2
  10.  
  11. /*  Liste, in die ICs eingetragen werden, die aus Schleifen */
  12. /*  gezogen werden sollen.                                  */
  13. struct movlist{
  14.     struct movlist *next;
  15.     struct IC *IC;
  16.     struct flowgraph *target_fg;
  17.     int flags;
  18. };
  19.  
  20. struct movlist *first_mov,*last_mov;
  21.  
  22. int report_weird_code,report_suspicious_loops;
  23.  
  24. /*  Bitvektoren fuer schleifeninvariante ICs    */
  25. unsigned char *invariant,*inloop,*moved,*moved_completely;
  26. unsigned char *fg_tmp;
  27. unsigned char *not_movable;
  28. size_t bsize;
  29.  
  30.  
  31. /*  Liste, in die ICs fuer strength-reduction eingetragen   */
  32. /*  werden.                                                 */
  33. struct srlist{
  34.     struct srlist *next;
  35.     struct IC *ind_var;
  36.     struct IC *IC;
  37.     struct flowgraph *target_fg;
  38.     /*  Hilfsvariable, falls eine aequivalente Operation schon reduziert    */
  39.     /*  wurde.                                                              */
  40.     struct Var *hv;
  41. };
  42.  
  43. struct srlist *first_sr,*last_sr;
  44.  
  45. /*  Liste, in die Daten fuer loop-unrolling eingetragen werden. */
  46. struct urlist{
  47.     int flags;
  48.     long total,unroll;
  49.     struct IC *cmp,*branch,*ind;
  50.     struct flowgraph *start,*head;
  51.     struct urlist *next;
  52. } *first_ur;
  53.  
  54. #define UNROLL_COMPLETELY 1
  55. #define UNROLL_MODULO 2
  56. #define UNROLL_INVARIANT 3
  57.  
  58. /*  Hier werden Induktionsvariablen vermerkt    */
  59. struct IC **ind_vars;
  60.  
  61. static struct flowgraph *first_fg;
  62.  
  63. int loops(struct flowgraph *fg,int footers)
  64. /*  kennzeichnet Schleifen im Flussgraph; wenn footers!=0 werden darf eine  */
  65. /*  Schleife nur einen gemeinsamen Austrittspunkt haben                     */
  66. {
  67.     int i,start,end,c=0;struct flowlist *lp;struct flowgraph *g,*loopend;
  68.     if(DEBUG&1024) printf("searching loops\n");
  69.     g=fg;
  70.     while(g){
  71.         start=g->index;
  72.         end=-1;
  73.         for(lp=g->in;lp;lp=lp->next){
  74.             if(!lp->graph) continue;
  75.             if(lp->graph->branchout==g||!lp->graph->end||lp->graph->end->code!=BRA){
  76.                 i=lp->graph->index;
  77.                 if(i>=start&&i>end){ end=i;loopend=lp->graph; }
  78.             }
  79.         }
  80.         if(end>=0){
  81.         /*  Schleife oder etwas aehnliches  */
  82.             struct flowgraph *p=g;
  83.             if(DEBUG&1024) printf("found possible loop from blocks %d to %d\n",start,end);
  84.             if(1/*goto_used*/){
  85.                 if(DEBUG&1024) printf("have to check...\n");
  86.                 do{
  87.                     if(!p||p->index>end) break;
  88.  
  89.                     /*  testen, ob aus der Schleife gesprungen wird */
  90.                     if(p->branchout&&footers){
  91.                         i=p->branchout->index;
  92.                         if(i<start){
  93.                             end=-1;
  94.                             break;
  95.                         }
  96.                         if(i>end&&(DEBUG&1024)){
  97.                             puts("jump out of loop");
  98.                             if(p->branchout!=loopend->normalout){
  99.                                 puts("no break");
  100.                                 if(p->branchout->start->typf!=return_label) puts("no return");
  101.                             }
  102.                         }
  103.                         if(i>end&&p->branchout!=loopend->normalout&&p->branchout->start->typf!=return_label){
  104.                         /*  Sprung zu anderem als dem normalen Austritt oder return */
  105.                             end=-1;
  106.                             break;
  107.                         }
  108.                     }
  109.                     /*  testen, ob in die Schleife gesprungen wird  */
  110.                     if(p!=g){
  111.                         for(lp=p->in;lp;lp=lp->next){
  112.                             if(!lp->graph) continue;
  113.                             if(lp->graph->branchout==p){
  114.                                 i=lp->graph->index;
  115.                                 if(i<start){
  116.                                     if(report_weird_code){error(175);report_weird_code=0;}
  117.                                     end=-1;
  118.                                     break;
  119.                                 }
  120.                                 if(i>end){
  121.                                     end=-1;
  122.                                     break;
  123.                                 }
  124.                             }
  125.                         }
  126.                     }
  127.                     if(p->index==end) break;
  128.                     p=p->normalout;
  129.                 }while(end>=0);
  130.             }else{
  131.                 if(DEBUG&1024) printf("must be a loop, because there was no goto\n");
  132.             }
  133.         }
  134.         if(end>=0){
  135.             if(DEBUG&1024) printf("confirmed that it is a loop\n");
  136.             g->loopend=loopend;
  137.             c++;
  138.         }
  139.         g=g->normalout;
  140.     }
  141.     return(c);
  142. }
  143.  
  144. struct flowgraph *create_loop_headers(struct flowgraph *fg,int av)
  145. /*  Fuegt vor jede Schleife einen Kopf-Block ein, wenn noetig.  */
  146. /*  Wenn av!=0 werden aktive Variablen korrekt uebertragen und  */
  147. /*  diverse Registerlisten uebernommen und index=-1 gesetzt.    */
  148. /*  Kann einen Block mehrmals in der ->in Liste eintragen       */
  149. {
  150.     struct flowgraph *g,*last,*new,*rg=fg;
  151.     struct IC *lic,*lastic;
  152.     if(DEBUG&1024) printf("creating loop-headers\n");
  153.     g=fg;last=0;lastic=0;
  154.     while(g){
  155.         new=0;
  156.         if(g->loopend){
  157.             if(!last){
  158.                 struct flowlist *lp;
  159.                 new=mymalloc(sizeof(struct flowgraph));
  160.                 rg=new;
  161.                 new->in=0;
  162.                 new->start=new->end=0;
  163.                 lp=mymalloc(sizeof(struct flowlist));
  164.                 lp->graph=new;
  165.                 lp->next=g->in;
  166.                 g->in=lp;
  167.             }else{
  168.                 struct flowlist *lp,*nl,**ls;
  169.                 new=mymalloc(sizeof(struct flowgraph));
  170.                 last->normalout=new;
  171.                 lic=mymalloc(ICS);
  172.                 lic->line=0;
  173.                 lic->file=0;
  174.                 new->start=new->end=lic;
  175.                 lic->code=LABEL;
  176.                 lic->typf=++label;
  177.                 lic->q1.flags=lic->q2.flags=lic->z.flags=0;
  178.                 lic->q1.am=lic->q2.am=lic->z.am=0;
  179.                 lic->use_cnt=lic->change_cnt=0;
  180.                 lic->use_list=lic->change_list=0;
  181.                 if(lastic) lastic->next=lic;
  182.                     else   first_ic=lic;
  183.                 lic->prev=lastic;
  184.                 g->start->prev=lic;
  185.                 lic->next=g->start;
  186.                 lp=g->in;ls=&new->in;
  187.                 while(lp){
  188.                     if(lp->graph&&lp->graph->index<g->index){
  189.                     /*  Eintritt von oben soll in den Kopf  */
  190.                         nl=mymalloc(sizeof(struct flowlist));
  191.                         nl->graph=lp->graph;
  192.                         nl->next=0;
  193.                         (*ls)=nl;
  194.                         ls=&nl->next;
  195.                         if(lp->graph->branchout==g){
  196.               struct IC *p=lp->graph->end;
  197.               if(DEBUG&1024) printf("changing branch\n");
  198.               while(p&&p->code==FREEREG) p=p->prev;
  199.               if(!p||p->code<BEQ||p->code>BRA) ierror(0);
  200.               p->typf=lic->typf;
  201.               lp->graph->branchout=new;
  202.                         }
  203.                         lp->graph=new;
  204.                     }
  205.                     lp=lp->next;
  206.                 }
  207.                 if(!new->in) ierror(0);
  208.             }
  209.             if(new){
  210.                 if(DEBUG&1024) printf("must insert loop-header before block %d\n",g->index);
  211.                 basic_blocks++;
  212.                 new->branchout=0;
  213.                 new->loopend=0;
  214.                 if(av)
  215.                     new->index=-1;
  216.                 else
  217.                     new->index=basic_blocks;
  218.                 new->normalout=g;
  219.                 new->calls=0;
  220.                 new->loop_calls=0;
  221.                 new->rd_in=new->rd_out=new->rd_kill=new->rd_gen=0;
  222.                 new->ae_in=new->ae_out=new->ae_kill=new->ae_gen=0;
  223.                 new->cp_in=new->cp_out=new->cp_kill=new->cp_gen=0;
  224.                 if(!av){
  225.                     new->av_in=new->av_out=new->av_kill=new->av_gen=0;
  226.                 }else{
  227.                     new->av_in=mymalloc(vsize);
  228.                     new->av_out=mymalloc(vsize);
  229.                     new->av_gen=mymalloc(vsize);
  230.                     new->av_kill=mymalloc(vsize);
  231.                     memset(new->av_gen,0,vsize);
  232.                     memset(new->av_kill,0,vsize);
  233.                     memcpy(new->av_out,g->av_in,vsize);
  234.                     memcpy(new->av_in,g->av_in,vsize);
  235.                     memcpy(&new->regv,&g->regv,sizeof(new->regv));
  236.                     memcpy(&new->regused,&g->regused,sizeof(new->regused));
  237.                 }
  238.             }
  239.         }
  240.         last=g;if(last->end) lastic=last->end;
  241.         g=g->normalout;
  242.     }
  243.     return(rg);
  244. }
  245. struct flowgraph *create_loop_footers(struct flowgraph *fg,int av)
  246. /*  Fuegt hinter jede Schleife einen Fuss-Block ein, wenn noetig.   */
  247. /*  Wenn av!=0 werden aktive Variablen korrekt uebertragen und      */
  248. /*  diverse Registerlisten uebernommen und index auf -2 gesetzt.    */
  249. {
  250.     struct flowgraph *g,*loopend,*out,*new;
  251.     struct IC *lic;
  252.     if(DEBUG&1024) printf("creating loop-footers\n");
  253.     g=fg;
  254.     while(g){
  255.         new=0;
  256.         loopend=g->loopend;
  257.         if(loopend){
  258.             struct flowlist *lp,*nl,**ls;
  259.             out=loopend->normalout;
  260.             new=mymalloc(sizeof(struct flowgraph));
  261.             new->normalout=out;
  262.             loopend->normalout=new;
  263.             lic=mymalloc(ICS);
  264.             lic->line=0;
  265.             lic->file=0;
  266.             new->start=new->end=lic;
  267.             lic->code=LABEL;
  268.             lic->typf=++label;
  269.             lic->q1.flags=lic->q2.flags=lic->z.flags=0;
  270.             lic->q1.am=lic->q2.am=lic->z.am=0;
  271.             lic->use_cnt=lic->change_cnt=0;
  272.             lic->use_list=lic->change_list=0;
  273.             if(out) lp=out->in; else {lp=0;new->in=0;}
  274.             ls=&new->in;
  275.             while(lp){
  276.                 if(lp->graph&&lp->graph->index<=loopend->index&&lp->graph->index>=g->index){
  277.                 /*  Austritt aus Schleife soll in den Fuss  */
  278.                     nl=mymalloc(sizeof(struct flowlist));
  279.                     nl->graph=lp->graph;
  280.                     nl->next=0;
  281.                     (*ls)=nl;
  282.                     ls=&nl->next;
  283.                     if(lp->graph->branchout==out){
  284.               struct IC *p=lp->graph->end;
  285.               if(DEBUG&1024) printf("changing branch\n");
  286.               while(p&&p->code==FREEREG) p=p->prev;
  287.               if(!p||p->code<BEQ||p->code>BRA) ierror(0);
  288.               p->typf=lic->typf;
  289.               lp->graph->branchout=new;
  290.                     }
  291.                     lp->graph=new;
  292.                 }
  293.                 lp=lp->next;
  294.             }
  295.             if(out&&!new->in) ierror(0);
  296.             if(DEBUG&1024) printf("must insert loop-footer after block %d\n",loopend->index);
  297.             basic_blocks++;
  298.             new->branchout=0;
  299.             new->loopend=0;
  300.             if(av)
  301.                 new->index=-2;
  302.             else
  303.                 new->index=basic_blocks;
  304.             new->normalout=out;
  305.             new->calls=0;
  306.             new->loop_calls=0;
  307.             new->rd_in=new->rd_out=new->rd_kill=new->rd_gen=0;
  308.             new->ae_in=new->ae_out=new->ae_kill=new->ae_gen=0;
  309.             new->cp_in=new->cp_out=new->cp_kill=new->cp_gen=0;
  310.             if(!av){
  311.                 new->av_in=new->av_out=new->av_kill=new->av_gen=0;
  312.             }else{
  313.                 new->av_in=mymalloc(vsize);
  314.                 new->av_out=mymalloc(vsize);
  315.                 new->av_kill=mymalloc(vsize);
  316.                 new->av_gen=mymalloc(vsize);
  317.                 memset(new->av_gen,0,vsize);
  318.                 memset(new->av_kill,0,vsize);
  319.                 if(out){
  320.                     memcpy(new->av_out,out->av_in,vsize);
  321.                     memcpy(new->av_in,out->av_in,vsize);
  322.                 }else{
  323.                     memset(new->av_in,0,vsize);
  324.                     memset(new->av_out,0,vsize);
  325.                 }
  326.                 memcpy(&new->regv,&g->regv,sizeof(new->regv));
  327.                 memcpy(&new->regused,&g->regused,sizeof(new->regused));
  328.             }
  329.             insert_IC_fg(new,loopend->end,lic);
  330.         }
  331.         g=g->normalout;
  332.     }
  333.     return(fg);
  334. }
  335. void add_movable(struct IC *p,struct flowgraph *fg,int flags)
  336. /*  Fuegt IC p, das aus der Schleife in Block fg mit Flags flags    */
  337. /*  verschoben werden darf in eine Liste.                           */
  338. {
  339.     struct movlist *new=mymalloc(sizeof(*new));
  340.     new->IC=p;
  341.     new->target_fg=fg;
  342.     new->flags=flags;
  343.     new->next=0;
  344.     if(last_mov){
  345.         last_mov->next=new;
  346.         last_mov=new;
  347.     }else{
  348.         first_mov=last_mov=new;
  349.     }
  350.     BSET(moved,p->defindex);
  351.     if(flags==MOVE_IC) BSET(moved_completely,p->defindex);
  352. }
  353. int move_to_head(void)
  354. /*  Geht die Liste mit verschiebbaren ICs durch und schiebt die ICs */
  355. /*  in den Vorkopf der Schleife. Ausserdem wird die Liste           */
  356. /*  freigegeben.                                                    */
  357. /*  Der Rueckgabewert hat Bit 1 gesetzt, wenn ICs ganz verschoben   */
  358. /*  wurden und Bit 2, falls eine Berechnung mit Hilfsvariable vor   */
  359. /*  die Schleife gezogen wurde.                                     */
  360. {
  361.     struct IC **fglist; /* Letztes IC vor jedem Block   */
  362.     struct flowgraph *g;struct IC *p;struct movlist *m;
  363.     int changed=0;
  364.  
  365.     if(!first_mov) return(0);
  366.  
  367.     if(DEBUG&1024) printf("moving the ICs out of the loop\n");
  368.  
  369.     fglist=mymalloc((basic_blocks+1)*sizeof(*fglist));
  370.     p=0;
  371.     for(g=first_fg;g;g=g->normalout){
  372.         if(g->index>basic_blocks) ierror(0);
  373.         if(g->end) p=g->end;
  374.         fglist[g->index]=p;
  375.     }
  376.     while(first_mov){
  377.         p=first_mov->IC;
  378.         g=first_mov->target_fg;
  379.         if(first_mov->flags==MOVE_IC){
  380.             if(DEBUG&1024) {printf("moving IC out of loop:\n");pric2(stdout,p);}
  381.             if(!p->prev||!p->next) ierror(0);
  382.             p->next->prev=p->prev;
  383.             p->prev->next=p->next;
  384.             insert_IC_fg(g,fglist[g->index],p);
  385.             fglist[g->index]=p;
  386.             changed|=1;
  387.         }else if(1){
  388.             struct Typ *t=mymalloc(TYPS);
  389.             struct IC *new=mymalloc(ICS);
  390.             struct Var *v;
  391.             if(DEBUG&1024) {printf("moving computation out of loop:\n");pric2(stdout,p);}
  392.             if(p->code==ADDRESS||p->code==ADDI2P||p->code==SUBIFP) t->flags=POINTER;
  393.                 else t->flags=p->typf;
  394.             if(p->code==COMPARE||p->code==TEST) t->flags=0;
  395.             if((t->flags&NQ)==POINTER){
  396.                 t->next=mymalloc(TYPS);
  397.                 t->next->flags=VOID;
  398.                 t->next->next=0;
  399.             }else t->next=0;
  400.             v=add_tmp_var(t);
  401.             *new=*p;
  402.             new->z.flags=VAR;
  403.             new->z.v=v;
  404.             new->z.val.vlong=l2zl(0L);
  405.             /*  Die neue Operation benutzt maximal, was die andere benutzte */
  406.             /*  und aendert nur die Hilfsvariable.                          */
  407.             if(have_alias){
  408.                 new->use_cnt=p->use_cnt;
  409.                 new->use_list=mymalloc(new->use_cnt*VLS);
  410.                 memcpy(new->use_list,p->use_list,new->use_cnt*VLS);
  411.                 new->change_cnt=1;
  412.                 new->change_list=mymalloc(VLS);
  413.                 new->change_list[0].v=v;
  414.                 new->change_list[0].flags=0;
  415.             }
  416.             insert_IC_fg(g,fglist[g->index],new);
  417.             fglist[g->index]=new;
  418.             p->code=ASSIGN;
  419.             p->typf=t->flags;
  420.             p->q1.flags=VAR;
  421.             p->q1.v=v;
  422.             p->q1.val.vlong=l2zl(0L);
  423.             p->q2.flags=0;
  424.             p->q2.val.vlong=szof(t);
  425.             /*  Die Operation in der Schleife benutzt nun zusaetzlich   */
  426.             /*  noch die Hilfsvariable.                                 */
  427.             if(have_alias){
  428.                 void *m=p->use_list;
  429.                 p->use_cnt++;
  430.                 p->use_list=mymalloc(p->use_cnt*VLS);
  431.                 memcpy(&p->use_list[1],m,(p->use_cnt-1)*VLS);
  432.                 free(m);
  433.                 p->use_list[0].v=v;
  434.                 p->use_list[0].flags=0;
  435.             }
  436.             changed|=2;
  437.         }
  438.         m=first_mov->next;
  439.         free(first_mov);
  440.         first_mov=m;
  441.     }
  442.     if(DEBUG&1024) print_flowgraph(first_fg);
  443.     free(fglist);
  444.     return(changed);
  445. }
  446. void calc_movable(struct flowgraph *start,struct flowgraph *end)
  447. /*  Berechnet, welche Definitionen nicht aus der Schleife start-end     */
  448. /*  verschoben werden duerfen. Eine Def. p von z darf nur verschoben    */
  449. /*  werden, wenn keine andere Def. von p existiert und alle             */
  450. /*  Verwendungen von z nur von p erreicht werden.                       */
  451. /*  Benutzt rd_defs, rd_tmp, rd_vars.                                   */
  452. {
  453.     struct flowgraph *g;struct IC *p;
  454.     int i,j,k,d;
  455.     unsigned char *changed_vars;
  456.     if(DEBUG&1024) printf("calculating not_movable for blocks %d to %d\n",start->index,end->index);
  457.     if(!(optflags&1024)){
  458.         memset(not_movable,UCHAR_MAX,dsize);
  459.         return;
  460.     }
  461.     memset(not_movable,0,dsize);
  462.     changed_vars=mymalloc(vsize);
  463.     memset(changed_vars,0,vsize);
  464.     for(g=start;g;g=g->normalout){
  465.         if(!g->rd_in) ierror(0);
  466.         memcpy(rd_defs,g->rd_in,dsize);
  467.         for(p=g->start;p;p=p->next){
  468.             for(j=0;j<p->change_cnt;j++){
  469.                 i=p->change_list[j].v->index;
  470.                 if(p->change_list[j].flags&DREFOBJ) i+=vcount-rcount;
  471.                 if(i>=vcount) continue;
  472.                 if(BTST(changed_vars,i)){
  473.                     bvunite(not_movable,defs[i],dsize);
  474.                 }else{
  475.                     BSET(changed_vars,i);
  476.                 }
  477.             }
  478.             for(k=0;k<p->use_cnt;k++){
  479.                 i=p->use_list[k].v->index;
  480.                 if(p->use_list[k].flags&DREFOBJ) i+=vcount-rcount;
  481.                 if(i>=vcount) continue;
  482.                 if(BTST(rd_defs,i+dcount+1)){   /*  undefined->i ?  */
  483.                     bvunite(not_movable,defs[i],dsize);
  484.                 }else{
  485.                     memcpy(rd_tmp,rd_defs,dsize);
  486.                     bvdiff(rd_tmp,defs[i],dsize);
  487.                     for(d=-1,j=0;j<=dcount;j++){
  488.                         if(BTST(rd_defs,j)){
  489.                             if(d>=0){  /*  mehr als eine Def.  */
  490.                                 bvunite(not_movable,defs[i],dsize);
  491.                                 d=-1;break;
  492.                             }else d=j;
  493.                         }
  494.                     }
  495.                     if(d>=0){
  496.                         memcpy(rd_tmp,defs[i],dsize);
  497.                         BCLR(rd_tmp,j);
  498.                         bvunite(not_movable,rd_tmp,dsize);
  499.                     }
  500.                 }
  501.             }
  502.  
  503.             /*  Das hier, um rd_defs zu aktualisieren.  */
  504.             rd_change(p);
  505.             if(p==g->end) break;
  506.         }
  507.         if(g==end) break;
  508.     }
  509.     free(changed_vars);
  510. }
  511. int used_in_loop_only(struct flowgraph *start,struct flowgraph *end,struct obj *o)
  512. /*  Testet, ob Variable nur in der Schleife benutzt wird.               */
  513. /*  Z.Z. wird nur auf Hilfsvariablen getestet.                          */
  514. /*  Unbedingt aendern!                                                  */
  515. {
  516.     struct Var *v;struct flowgraph *g;struct IC *p;
  517.     if((o->flags&(VAR|DREFOBJ))!=VAR) return(0);
  518.     v=o->v;
  519.     if((v->flags&USEDASADR)||v->nesting==0||v->storage_class==EXTERN||v->storage_class==STATIC)
  520.         return(0);
  521.     for(g=first_fg;g;g=g->normalout){
  522.         if(g==start) g=end->normalout;
  523.         if(!g) break;
  524.         for(p=g->start;p;p=p->next){
  525.             if((p->q1.flags&VAR)&&p->q1.v==v) return(0);
  526.             if((p->q2.flags&VAR)&&p->q2.v==v) return(0);
  527.             if((p->z.flags&VAR)&&p->z.v==v) return(0);
  528.             if(p==g->end) break;
  529.         }
  530.         if(g==end) break;
  531.     }
  532.     return(1);
  533. }
  534.  
  535. int always_reached(struct flowgraph *start,struct flowgraph *end,struct flowgraph *fg,struct IC *z,int ignorecall)
  536. /*  Testet, ob z immer ausgefuehrt wird, falls start in fg ausgefuehrt  */
  537. /*  wird. fg_tmp ist ein Bitvektor, um zu merken, welche Bloecke sicher */
  538. /*  zu z fuehren. Das ganze fuer die Schleife start-end.                */
  539. /*  Wenn ignorecall!=0 ist, wird angenommen, dass jeder CALL            */
  540. /*  zurueckkehrt (das ist nuetzlich fuer loop-unrolling).               */
  541. {
  542.     unsigned char *bmk=fg_tmp;
  543.     struct IC *p;struct flowgraph *g;
  544.     int changed;
  545.  
  546.     for(p=z;p;p=p->prev){
  547.         if(!ignorecall&&p->code==CALL) return(0);
  548.         if(p==fg->start) break;
  549.     }
  550.  
  551.     if(fg==start) return(1);
  552.  
  553.     memset(bmk,0,bsize);
  554.     BSET(bmk,fg->index);
  555.  
  556.     do{
  557.         changed=0;
  558.         for(g=start;g;g=g->normalout){
  559.             if(!BTST(bmk,g->index)){
  560.                 struct flowgraph *n=g->normalout;
  561.                 struct flowgraph *b=g->branchout;
  562.                 if(n||b){
  563.                     if((!b||BTST(bmk,b->index))&&
  564.                        (!n||(g->end&&g->end->code==BRA)||BTST(bmk,n->index))){
  565.                         for(p=g->end;p;p=p->prev){
  566.                             if(!ignorecall&&p->code==CALL) break;
  567.                             if(p==g->start){
  568.                                 if(g==start) return(1);
  569.                                 changed=1; BSET(bmk,g->index);
  570.                                 break;
  571.                             }
  572.                         }
  573.                     }
  574.                 }
  575.             }
  576.             if(g==end) break;
  577.         }
  578.     }while(changed);
  579.     return(0);
  580. }
  581.  
  582. int def_invariant(int vindex,int ignore)
  583. /*  Ermittelt, ob Variable vindex schleifeninvariant unter den Bedingungen  */
  584. /*  rd_defs, inloop und invariant ist.                                      */
  585. /*  Definition ignore wird nicht beachtet. Wenn ignore auf eine gueltige    */
  586. /*  Definition gesetzt wird, kann man somit auf Induktionsvariablen testen  */
  587. /*  (das Ergebnis sagt dann, ob das die einzige Definition in der Schleife  */
  588. /*  ist).                                                                   */
  589. {
  590.     int i,k,j,d=0;
  591. /*    printf("def_inv(%d)=%s(%ld)\n",vindex,vilist[vindex]->identifier,zl2l(vilist[vindex]->offset));*/
  592.     if(!BTST(rd_defs,vindex+dcount+1)){
  593.         memcpy(rd_tmp,rd_defs,dsize);
  594.         bvintersect(rd_tmp,defs[vindex],dsize);
  595.         for(j=1;j<=dcount;j++){
  596.             if(j!=ignore&&BTST(rd_tmp,j)&&BTST(inloop,j)){
  597.                 /*  Mehr als eine moegliche Def. innerhalb der Schleife oder    */
  598.                 /*  eine invariante Def. in der Schleife => nicht invariant.    */
  599.                 if(d) return(0);
  600.                 if(!BTST(moved_completely,j)) return(0);
  601.                 d=1;
  602.             }
  603.         }
  604.     }else{
  605.         for(j=1;j<=dcount;j++){
  606.             if(j!=ignore&&BTST(rd_defs,j)&&BTST(inloop,j)){
  607.                 struct IC *p=dlist[j];
  608.                 for(k=0;k<p->change_cnt;k++){
  609.                     i=p->change_list[k].v->index;
  610.                     if(p->change_list[k].flags&DREFOBJ) i+=vcount-rcount;
  611. /*                    printf("modifies %d\n",i);*/
  612.                     if(i==vindex) break;
  613.                 }
  614.                 if(k>=p->change_cnt) continue;
  615.                 /*  Mehr als eine moegliche Def. innerhalb der Schleife oder    */
  616.                 /*  eine invariante Def. in der Schleife => nicht invariant.    */
  617.                 if(d) return(0);
  618.                 if(!BTST(moved_completely,j)) return(0);
  619.                 d=1;
  620.             }
  621.         }
  622.     }
  623.     return(1);
  624. }
  625.  
  626. void frequency_reduction(struct flowgraph *start,struct flowgraph *end,struct flowgraph *head)
  627. /*  Schleifeninvariante ICs finden und in eine Liste eintragen, falls   */
  628. /*  sie vor die Schleife gezogen werden koennen.                        */
  629. {
  630.     struct IC *p;struct flowgraph *g;
  631.  
  632.  
  633.     int i,changed;
  634.  
  635.     if(head&&start->loopend){
  636.         end=start->loopend;
  637.  
  638.         if(DEBUG&1024){
  639.             printf("searching for loop-invariant code in loop from block %d to %d\n",start->index,end->index);
  640.             printf("head_fg=%d\n",head->index);
  641.         }
  642.         calc_movable(start,end);
  643.         /*  erstmal kein IC invariant   */
  644.         memset(invariant,0,dsize);
  645.  
  646.         /*  kennzeichnen, welche ICs in der Schleife liegen */
  647.         memset(inloop,0,dsize);
  648.         for(g=start;g;g=g->normalout){
  649.             for(p=g->start;p;p=p->next){
  650.                 if(p->defindex) BSET(inloop,p->defindex);
  651.                 if(p==g->end) break;
  652.             }
  653.             if(g==end) break;
  654.         }
  655.  
  656.         do{
  657.             changed=0;
  658.             if(DEBUG&1024) printf("loop-invariant pass\n");
  659.  
  660.             /*  Schleifeninvariante ICs suchen  */
  661.  
  662.             for(g=start;g;g=g->normalout){
  663.                 memcpy(rd_defs,g->rd_in,dsize);
  664.                 for(p=g->start;p;p=p->next){
  665.                     int k1,k2;
  666.                     /*  testen, ob IC neu als invariant markiert werden kann    */
  667.                     if(p->defindex&&p->code!=CALL&&p->code!=GETRETURN&&!BTST(invariant,p->defindex)){
  668.                         if(!BTST(inloop,p->defindex)) ierror(0);
  669.                         if(p->code==ADDRESS||!p->q1.flags||(p->q1.flags&KONST)||(p->q1.flags&VARADR)){
  670.                             k1=1;
  671.                         }else{
  672.                             if(!(p->q1.flags&VAR)) ierror(0);
  673.                             i=p->q1.v->index;
  674.                             if(p->q1.flags&DREFOBJ) i+=vcount-rcount;
  675.                             k1=def_invariant(i,-1);
  676.                         }
  677.                         if(k1){
  678.                             if(!p->q2.flags||(p->q2.flags&KONST)||(p->q2.flags&VARADR)){
  679.                                 k2=1;
  680.                             }else{
  681.                                 if(!(p->q2.flags&VAR)) ierror(0);
  682.                                 i=p->q2.v->index;
  683.                                 if(p->q2.flags&DREFOBJ) i+=vcount-rcount;
  684.                                 k2=def_invariant(i,-1);
  685.                             }
  686.                         }
  687.                         if(k1&&k2){
  688. /*                            if(DEBUG&1024){ printf("found loop-invariant IC:\n");pric2(stdout,p);}*/
  689.                             if(!BTST(moved,p->defindex)&&(always_reached(start,end,g,p,0)||(!dangerous_IC(p)&&used_in_loop_only(start,end,&p->z)))){
  690.                                 if(p->z.flags&DREFOBJ)
  691.                                     k1=def_invariant(p->z.v->index,-1);
  692.                                 else
  693.                                     k1=1;
  694. /*                                if(DEBUG&1024) printf("always reached or used only in loop\n");*/
  695.                                 if(k1&&!BTST(not_movable,p->defindex)){
  696. /*                                    if(DEBUG&1024) printf("movable\n");*/
  697.                                     add_movable(p,head,MOVE_IC);
  698.                                 }else{
  699.                                     if(p->code==ADDRESS||((p->typf&NQ)<=POINTER&&(p->q2.flags||(p->q1.flags&DREFOBJ)))){
  700. /*                                        if(DEBUG&1024) printf("move computation out of loop\n");*/
  701.                                         add_movable(p,head,MOVE_COMP);
  702.                                     }
  703.                                 }
  704.                             }else{
  705.                             /*  Wenn IC immer erreicht wird oder ungefaehrlich  */
  706.                             /*  ist, kann man zumindest die Operation           */
  707.                             /*  rausziehen, falls das lohnt.                    */
  708.                                 if(!BTST(moved,p->defindex)&&(!dangerous_IC(p)&&(p->typf&NQ)<=POINTER&&(p->q2.flags||(p->q1.flags&DREFOBJ)||p->code==ADDRESS))){
  709. /*                                    if(DEBUG&1024) printf("move computation out of loop\n");*/
  710.                                     add_movable(p,head,MOVE_COMP);
  711.                                 }
  712.                             }
  713.                             BSET(invariant,p->defindex);
  714.                             changed=1;
  715.                         }
  716.                     }
  717.  
  718.                     /*  Das hier, um rd_defs zu aktualisieren.  */
  719.                     rd_change(p);
  720.  
  721.                     if(p==g->end) break;
  722.                 }
  723.                 if(g==end) break;
  724.             }
  725.         }while(changed);
  726.  
  727.     }
  728.     return;
  729. }
  730. void add_sr(struct IC *p,struct flowgraph *fg,int i_var)
  731. /*  Fuegt IC p, das aus der Schleife in Block fg lineare Fkt. der   */
  732. /*  Induktionsvariable i_var ist, in Liste ein.                     */
  733. /*  Funktioniert als Stack. Da mit aeusseren Schleifen angefangen   */
  734. /*  wird, werden ICs zuerst in inneren Schleifen reduziert. Da ein  */
  735. /*  IC nur einmal reduziert wird, sollte dadurch das Problem eines  */
  736. /*  ICs, das potentiell in mehreren Schleifen reduziert werden      */
  737. /*  koennte, geloest werden.                                        */
  738. {
  739.     struct srlist *new=mymalloc(sizeof(*new));
  740.     if(DEBUG&1024) printf("all:%p\n",(void*)new);
  741.     new->IC=p;
  742.     new->target_fg=fg;
  743.     new->ind_var=ind_vars[i_var];
  744.     new->next=first_sr;
  745.     new->hv=0;
  746.     first_sr=new;
  747. #if 0
  748.     if(last_sr){
  749.         last_sr->next=new;
  750.         last_sr=new;
  751.     }else{
  752.         first_sr=last_sr=new;
  753.     }
  754. #endif
  755. }
  756. int do_sr(void)
  757. /*  Durchlaufe die Liste aller strength-reduction-Kandidaten und    */
  758. /*  ersetze sie durch neue Induktionsvariablen. Dabei aufpassen,    */
  759. /*  falls ein IC schon von frequency-reduction bearbeitet wurde.    */
  760. /*  Ausserdem wird die Liste freigegeben.                           */
  761. {
  762.     struct IC **fglist; /* Letztes IC vor jedem Block   */
  763.     struct IC *p;
  764.     struct flowgraph *g;
  765.     struct srlist *mf;
  766.     int changed=0;
  767.  
  768.     if(!first_sr) return(0);
  769.  
  770.     if(DEBUG&1024) printf("performing strength-reductions\n");
  771.  
  772.     fglist=mymalloc((basic_blocks+1)*sizeof(*fglist));
  773.     p=0;
  774.     for(g=first_fg;g;g=g->normalout){
  775.         if(g->index>basic_blocks) ierror(0);
  776.         if(g->end) p=g->end;
  777.         fglist[g->index]=p;
  778.     }
  779.  
  780.     while(first_sr){
  781.         struct Var *niv,*nstep;
  782.         struct Typ *t1,*t2;
  783.         struct IC *iv_ic,*new,*m;
  784.         int i,c;
  785.         p=first_sr->IC;
  786.         i=p->defindex;
  787.         /*  Falls IC noch nicht verschoben und noch nicht reduziert wurde.  */
  788.         if(!BTST(moved,i)&&p->code!=ASSIGN){
  789.             if(first_sr->hv){
  790.             /*  Es wurde schon eine aequivalente Operation reduziert, wir   */
  791.             /*  koennen also dieselbe Hilfsvariable benutzen.               */
  792.                 p->code=ASSIGN;
  793.                 p->q1.flags=VAR;
  794.                 p->q1.v=first_sr->hv;
  795.                 p->q1.val.vlong=l2zl(0L);
  796.                 p->q2.flags=0;
  797.                 p->q2.val.vlong=szof(p->z.v->vtyp);
  798.                 /*  Hilfsvariable wird jetzt auch benutzt.  */
  799.                 if(have_alias){
  800.                     void *m=p->use_list;
  801.                     p->use_cnt++;
  802.                     p->use_list=mymalloc(p->use_cnt*VLS);
  803.                     memcpy(&p->use_list[1],m,(p->use_cnt-1)*VLS);
  804.                     free(m);
  805.                     p->use_list[0].v=first_sr->hv;
  806.                     p->use_list[0].flags=0;
  807.                 }
  808.             }else{
  809.                 int minus=0;
  810.                 if(DEBUG&1024){ printf("performing strength-reduction on IC:\n");pric2(stdout,p);}
  811.                 c=p->code;
  812.                 g=first_sr->target_fg;
  813.                 iv_ic=first_sr->ind_var;
  814.                 /*  Merken, wenn IC von der Form SUB x,ind_var->z   */
  815.                 if(c==SUB&&!compare_objs(&p->q2,&iv_ic->z,iv_ic->typf))
  816.                     minus=1;
  817. if(DEBUG&1024) puts("1");
  818.                 t1=mymalloc(TYPS);
  819.                 t1->flags=p->typf;
  820.                 if(c==ADDI2P||c==SUBIFP){
  821.                     t1->flags=POINTER;
  822.                     t1->next=mymalloc(TYPS);
  823.                     t1->next->flags=VOID;
  824.                     t1->next->next=0;
  825.                 }else t1->next=0;
  826.                 niv=add_tmp_var(t1);
  827. if(DEBUG&1024) puts("2");
  828.                 /*  Suchen, ob es noch aequivalente Operationen gibt.   */
  829.                 /*  Noch sehr ineffizient...                            */
  830.                 for(mf=first_sr->next;mf;mf=mf->next){
  831.                     if(mf->target_fg==g&&mf->ind_var==iv_ic){
  832.                         m=mf->IC;
  833.                         if(c==m->code&&p->typf==m->typf&&
  834.                            !compare_objs(&p->q1,&m->q1,p->typf)&&
  835.                            !compare_objs(&p->q2,&m->q2,p->typf)){
  836.                             if(mf->hv) ierror(0);
  837.                             mf->hv=niv;
  838.                             if(DEBUG&1024){ printf("equivalent operation\n");pric2(stdout,m);}
  839.                         }
  840.                     }
  841.                 }
  842. if(DEBUG&1024) puts("3");
  843.                 /*  Initialisierung der Hilfsinduktionsvariablen    */
  844.                 new=mymalloc(ICS);
  845.                 *new=*p;
  846.                 new->z.flags=VAR;
  847.                 new->z.v=niv;
  848.                 new->z.val.vlong=l2zl(0L);
  849.                 /*  IC benutzt dasselbe wie p und aendert nur niv.  */
  850. if(DEBUG&1024) puts("4");
  851.                 if(have_alias){
  852.                     new->change_cnt=1;
  853.                     new->change_list=mymalloc(VLS);
  854.                     new->change_list[0].v=niv;
  855.                     new->change_list[0].flags=0;
  856.                     new->use_cnt=p->use_cnt;
  857.                     new->use_list=mymalloc(new->use_cnt*VLS);
  858.                     memcpy(new->use_list,p->use_list,new->use_cnt*VLS);
  859.                 }
  860. if(DEBUG&1024) puts("5");
  861.                 insert_IC_fg(g,fglist[g->index],new);
  862.                 fglist[g->index]=m=new;
  863. if(DEBUG&1024) puts("6");
  864.                 /*  Ersetzen der Operation durch die Hilfsvariable  */
  865.                 p->code=ASSIGN;
  866.                 p->typf=t1->flags;
  867.                 p->q1=m->z;
  868.                 p->q2.flags=0;
  869.                 p->q2.val.vlong=szof(t1);
  870.                 /*  Benutzt jetzt auch Hilfsvariable.               */
  871. if(DEBUG&1024) puts("7");
  872.                 if(have_alias){
  873.                     void *mr=p->use_list;
  874.                     p->use_cnt++;
  875.                     p->use_list=mymalloc(p->use_cnt*VLS);
  876.                     memcpy(&p->use_list[1],mr,(p->use_cnt-1)*VLS);
  877.                     free(mr);
  878.                     p->use_list[0].v=niv;
  879.                     p->use_list[0].flags=0;
  880.                 }
  881. if(DEBUG&1024) puts("8");
  882.                 /*  Berechnen der Schrittweite fuer Hilfsvariable   */
  883.                 if(c==MULT){
  884.                     t2=mymalloc(TYPS);
  885.                     t2->flags=iv_ic->typf;
  886.                     t2->next=0;
  887.                     nstep=add_tmp_var(t2);
  888.                     new=mymalloc(ICS);
  889.                     new->line=iv_ic->line;
  890.                     new->file=iv_ic->file;
  891.                     new->code=MULT;
  892.                     new->typf=p->typf;
  893.                     new->z.flags=VAR;
  894.                     new->z.v=nstep;
  895.                     new->z.val.vlong=l2zl(0L);
  896.                     if(!compare_objs(&m->q1,&iv_ic->z,iv_ic->typf)) new->q1=m->q2;
  897.                         else new->q1=m->q1;
  898.                     if(!compare_objs(&iv_ic->q1,&iv_ic->z,iv_ic->typf)) new->q2=iv_ic->q2;
  899.                         else new->q2=iv_ic->q1;
  900.                     /*  Benutzt dasselbe wie iv_ic und m.   */
  901.                     if(have_alias){
  902.                         new->use_cnt=iv_ic->use_cnt+m->use_cnt;
  903.                         new->use_list=mymalloc(new->use_cnt*VLS);
  904.                         memcpy(new->use_list,iv_ic->use_list,iv_ic->use_cnt*VLS);
  905.                         memcpy(&new->use_list[iv_ic->use_cnt],m->use_list,m->use_cnt*VLS);
  906.                         new->change_cnt=1;
  907.                         new->change_list=mymalloc(VLS);
  908.                         new->change_list[0].v=nstep;
  909.                         new->change_list[0].flags=0;
  910.                     }
  911.                     insert_IC_fg(g,fglist[g->index],new);
  912.                     fglist[g->index]=m=new;
  913.                 }
  914. if(DEBUG&1024) puts("9");
  915.                 /*  Erhoehen der Hilfsvariable um Schrittweite      */
  916.                 new=mymalloc(ICS);
  917.                 new->line=iv_ic->line;
  918.                 new->file=iv_ic->file;
  919.  
  920.                 new->code=iv_ic->code;
  921. if(DEBUG&1024) puts("10");
  922.                 if(minus){
  923.                     switch(new->code){
  924.                         case ADD:     new->code=SUB; break;
  925.                         case SUB:     new->code=ADD; break;
  926.                         case ADDI2P:  new->code=SUBIFP; break;
  927.                         case SUBIFP:  new->code=ADDI2P; break;
  928.                     }
  929.                 }
  930. if(DEBUG&1024) puts("11");
  931.                 if(t1->flags==POINTER){
  932.                     if(new->code==ADD) new->code=ADDI2P;
  933.                     if(new->code==SUB) new->code=SUBIFP;
  934.                 }
  935. if(DEBUG&1024) puts("12");
  936.                 new->typf=iv_ic->typf;
  937.                 new->q1.flags=VAR;
  938.                 new->q1.v=niv;
  939.                 new->q1.val.vlong=l2zl(0L);
  940.                 new->z=new->q1;
  941.                 if(c==MULT){
  942.                     new->q2=m->z;
  943.                 }else{
  944.                     if(!compare_objs(&iv_ic->q1,&iv_ic->z,iv_ic->typf)) new->q2=iv_ic->q2;
  945.                         else new->q2=iv_ic->q1;
  946.                 }
  947. if(DEBUG&1024) puts("13");
  948.                 if(have_alias){
  949.                     new->use_cnt=iv_ic->use_cnt+m->use_cnt;
  950.                     new->use_list=mymalloc(new->use_cnt*VLS);
  951.                     memcpy(new->use_list,iv_ic->use_list,iv_ic->use_cnt*VLS);
  952.                     memcpy(&new->use_list[iv_ic->use_cnt],m->use_list,m->use_cnt*VLS);
  953.                     new->change_cnt=1;
  954.                     new->change_list=mymalloc(VLS);
  955.                     new->change_list[0].v=niv;
  956.                     new->change_list[0].flags=0;
  957.                 }
  958. if(DEBUG&1024) puts("14");
  959.                 /*  Flussgraph muss nur bei den Schleifenkoepfen ok sein.   */
  960.                 insert_IC(iv_ic,new);
  961. if(DEBUG&1024) puts("15");
  962.                 changed|=2;
  963.             }
  964.         }
  965. if(DEBUG&1024) puts("16");
  966.         mf=first_sr->next;
  967. if(DEBUG&1024) puts("16a");
  968. if(DEBUG&1024) printf("fr:%p\n",(void*)first_sr);
  969.         free(first_sr);
  970. if(DEBUG&1024) puts("16b");
  971.         first_sr=mf;
  972. if(DEBUG&1024) puts("17");
  973.     }
  974.     free(fglist);
  975.     return(changed);
  976. }
  977. void strength_reduction(struct flowgraph *start,struct flowgraph *end,struct flowgraph *head)
  978. /*  Ersetzen von Operationen mit einer Induktionsvariablen und einem    */
  979. /*  schleifeninvarianten Operanden durch eine zusaetzliche              */
  980. /*  Hilfsinduktionsvariable.                                            */
  981. {
  982.     struct flowgraph *g;struct IC *p;
  983.     int i;
  984.     if(DEBUG&1024) printf("performing strength_reduction on blocks %d to %d\n",start->index,end->index);
  985.     for(i=0;i<vcount;i++) ind_vars[i]=0;
  986.     /*  Nach Induktionsvariablen suchen.    */
  987.     for(g=start;g;g=g->normalout){
  988.         memcpy(rd_defs,g->rd_in,dsize);
  989.         for(p=g->start;p;p=p->next){
  990.             int c=p->code;
  991.             if(c==ADD||c==ADDI2P||c==SUB||c==SUBIFP){
  992.                 if(!compare_objs(&p->q1,&p->z,p->typf)){
  993. /*                    if(DEBUG&1024){printf("possible induction:\n");pric2(stdout,p);}*/
  994.                     if(p->q2.flags&VAR){
  995.                         i=p->q2.v->index;
  996.                         if(p->q2.flags&DREFOBJ) i+=vcount-rcount;
  997.                     }
  998.                     if((p->q2.flags&(VAR|VARADR))!=VAR||def_invariant(i,-1)){
  999.                         i=p->z.v->index;
  1000.                         if(p->z.flags&DREFOBJ) i+=vcount-rcount;
  1001.                         if(def_invariant(i,p->defindex)){
  1002. /*                            if(DEBUG&1024) {printf("found basic induction var:\n");pric2(stdout,p);}*/
  1003.                             ind_vars[i]=p;
  1004.                         }
  1005.                     }
  1006.                 }
  1007.                 if(USEQ2ASZ&&c!=SUB&&c!=SUBIFP&&!compare_objs(&p->q2,&p->z,p->typf)){
  1008. /*                    if(DEBUG&1024){printf("possible induction:\n");pric2(stdout,p);}*/
  1009.                     if(p->q1.flags&VAR){
  1010.                         i=p->q1.v->index;
  1011.                         if(p->q1.flags&DREFOBJ) i+=vcount-rcount;
  1012.                     }
  1013.                     if((p->q1.flags&(VAR|VARADR))!=VAR||def_invariant(i,-1)){
  1014.                         i=p->z.v->index;
  1015.                         if(p->z.flags&DREFOBJ) i+=vcount-rcount;
  1016.                         if(def_invariant(i,p->defindex)){
  1017. /*                            if(DEBUG&1024) {printf("found basic induction var:\n");pric2(stdout,p);}*/
  1018.                             ind_vars[i]=p;
  1019.                         }
  1020.                     }
  1021.                 }
  1022.             }
  1023.  
  1024.             /*  Das hier, um rd_defs zu aktualisieren.  */
  1025.             rd_change(p);
  1026.  
  1027.             if(p==g->end) break;
  1028.         }
  1029.         if(g==end) break;
  1030.     }
  1031.     /*  Nach reduzierbaren Operationen suchen   */
  1032.     for(g=start;g;g=g->normalout){
  1033.         memcpy(rd_defs,g->rd_in,dsize);
  1034.         for(p=g->start;p;p=p->next){
  1035.             if((p->code==MULT||p->code==ADD||p->code==SUB||p->code==ADDI2P||p->code==SUBIFP)&&
  1036.                (((p->typf&NQ)!=FLOAT&&(p->typf&NQ)!=DOUBLE)||fp_assoc) ){
  1037.                 int k1,k2,iv;
  1038.                 if((p->q1.flags&(VAR|VARADR))==VAR){
  1039.                     i=p->q1.v->index;
  1040.                     if(p->q1.flags&DREFOBJ) i+=vcount-rcount;
  1041.                     if(ind_vars[i]) {k1=1;iv=i;}
  1042.                     else if(def_invariant(i,-1)) k1=2;
  1043.                     else k1=0;
  1044.                 }else k1=2;
  1045.                 if((p->q2.flags&(VAR|VARADR))==VAR){
  1046.                     i=p->q2.v->index;
  1047.                     if(p->q2.flags&DREFOBJ) i+=vcount-rcount;
  1048.                     if(ind_vars[i]) {k2=1;iv=i;}
  1049.                     else if(def_invariant(i,-1)) k2=2;
  1050.                     else k2=0;
  1051.                 }else k2=2;
  1052.                 if(p->z.flags&VAR){
  1053.                 /*  Aufpassen, dass eine Induktion nicht selbst reduziert   */
  1054.                 /*  wird.                                                   */
  1055.                     i=p->z.v->index;
  1056.                     if(p->z.flags&DREFOBJ) i+=vcount-rcount;
  1057.                     if(ind_vars[i]) k1=0;
  1058.                 }
  1059.                 if(k1+k2==3){
  1060. /*                    if(DEBUG&1024) {printf("could perform strength-reduction on:\n");pric2(stdout,p);}*/
  1061.                     add_sr(p,head,iv);
  1062.                 }
  1063.             }
  1064.             /*  Das hier, um rd_defs zu aktualisieren.  */
  1065.             rd_change(p);
  1066.  
  1067.             if(p==g->end) break;
  1068.         }
  1069.         if(g==end) break;
  1070.     }
  1071. }
  1072. void copy_code(struct IC *start,struct IC *end,struct IC *dest,int n)
  1073. /*  Kopiert Code von start bis end n-mal hinter dest. Generiert         */
  1074. /*  entsprechend neue Labels. Allerdings wird der Flussgraph und        */
  1075. /*  aliasing-info nicht angepasst und muss danach neu generiert werden. */
  1076. {
  1077.     int firstl=0,lastl=0,*larray,i,j;
  1078.     struct IC *p,*new;
  1079.     if(DEBUG&1024) printf("copy_code %d times\n",n);
  1080.     /*  Feststellen, welche Labels in der Schleife definiert werden.    */
  1081.     for(p=start;p;p=p->next){
  1082.         if(p->code==LABEL){
  1083.             if(firstl==0||firstl>p->typf) firstl=p->typf;
  1084.             if(lastl ==0|| lastl<p->typf) lastl =p->typf;
  1085.         }
  1086.         if(p==end) break;
  1087.     }
  1088.     if(DEBUG&1024) printf("firstl=%d, lastl=%d\n",firstl,lastl);
  1089.     larray=mymalloc((lastl-firstl+1)*sizeof(*larray));
  1090.     for(i=0;i<=lastl-firstl;i++) larray[i]=0;
  1091.     for(p=start;p;p=p->next){
  1092.         if(p->code==LABEL) larray[p->typf-firstl]=1;
  1093.         if(p==end) break;
  1094.     }
  1095.     /*  Hauptschleife.  */
  1096.     for(i=0;i<n;i++){
  1097.         /*  Neue Labels erzeugen.   */
  1098.         for(j=0;j<=lastl-firstl;j++)
  1099.             if(larray[j]) larray[j]=++label;
  1100.         /*  Code kopieren (rueckwaerts).    */
  1101.         for(p=end;p;p=p->prev){
  1102.             new=mymalloc(ICS);
  1103.             *new=*p;
  1104.             /*  Fuer free_alias.    */
  1105.             new->change_cnt=new->use_cnt=0;
  1106.             /*  Evtl. Label anpassen.   */
  1107.             if(p->code>=LABEL&&p->code<=BRA){
  1108.                 if(p->typf>=firstl&&p->typf<=lastl&&larray[p->typf-firstl])
  1109.                     new->typf=larray[p->typf-firstl];
  1110.             }
  1111.             insert_IC(dest,new);
  1112.             if(p==start) break;
  1113.         }
  1114.     }
  1115.     free(larray);
  1116. }
  1117. void add_ur(int flags,long total,long unroll,struct flowgraph *start,struct flowgraph *head,struct IC *cmp,struct IC *branch,struct IC *ind)
  1118. /*  Fuegt Daten fuer loop-unrolling in Stack ein.                       */
  1119. {
  1120.     struct urlist *new=mymalloc(sizeof(struct urlist));
  1121.     if(DEBUG&1024) printf("add_ur, flags=%d\n",flags);
  1122.     new->flags=flags;
  1123.     new->total=total;
  1124.     new->unroll=unroll;
  1125.     new->start=start;
  1126.     new->head=head;
  1127.     new->cmp=cmp;
  1128.     new->branch=branch;
  1129.     new->ind=ind;
  1130.     new->next=first_ur;
  1131.     first_ur=new;
  1132. }
  1133. int do_unroll(int donothing)
  1134. /*  Fuehrt loop-unrolling durch. Wenn donothing!=0, wird die Liste nur  */
  1135. /*  freigegeben.                                                        */
  1136. {
  1137.     int changed=0; struct urlist *m;
  1138.     while(m=first_ur){
  1139.         int flags=m->flags;
  1140.         long total=m->total,unroll=m->unroll;
  1141.         struct flowgraph *start=m->start,*head=m->head;
  1142.         struct IC *cmp=m->cmp,*branch=m->branch,*ind=m->ind;
  1143.         if(donothing) flags=0;
  1144.         if(flags==UNROLL_COMPLETELY){
  1145.             /*  Schleife komplett ausrollen.    */
  1146.             if(DEBUG&1024) printf("unroll loop completely\n");
  1147.             copy_code(start->start->next,cmp->prev,start->start,total-1);
  1148.             if(DEBUG&1024) printf("removing loop branch\n");
  1149.             remove_IC(branch);
  1150.             if(!cmp->z.flags){
  1151.                 remove_IC(cmp);
  1152.                 if(DEBUG&1024) printf("removing loop compare\n");
  1153.             }
  1154.             changed|=1;
  1155.         }
  1156.         if(flags==UNROLL_MODULO){
  1157.             /*  Schleife teilweise ausrollen.   */
  1158.             if(DEBUG&1024) printf("unroll loop partially, n=%ld,r=%ld\n",unroll,total%unroll);
  1159.             if(unroll>1){
  1160.                 copy_code(start->start->next,cmp->prev,head->start,total%unroll);
  1161.                 copy_code(start->start->next,cmp->prev,start->start,unroll-1);
  1162.                 changed|=1;
  1163.             }
  1164.         }
  1165.         if(flags==UNROLL_INVARIANT){
  1166.             struct IC *new; struct Var *v; int out=++label,code;
  1167.             long i; struct Typ *t;
  1168.             if(DEBUG&1024) printf("unrolling non-constant loop\n");
  1169.             if(cmp->q1.flags&VAR) t=cmp->q1.v->vtyp; else t=cmp->q2.v->vtyp;
  1170.             v=add_tmp_var(clone_typ(t));
  1171.             /*  branch dient hier teilweise als leere Schablone.    */
  1172.             /*  Label an Schleifenausgang setzen.   */
  1173.             new=mymalloc(ICS); *new=*branch;
  1174.             new->change_cnt=new->use_cnt=0;
  1175.             new->code=LABEL;
  1176.             new->typf=out;
  1177.             insert_IC(branch,new);
  1178.             /*  Test vor die unroll-Variante.   */
  1179.             new=mymalloc(ICS); *new=*branch;
  1180.             new->change_cnt=new->use_cnt=0;
  1181.             if(branch->code==BLT) new->code=BGE;
  1182.             if(branch->code==BLE) new->code=BGT;
  1183.             if(branch->code==BGT) new->code=BLE;
  1184.             if(branch->code==BGE) new->code=BLT;
  1185.             if(branch->code==BEQ) new->code=BNE;
  1186.             if(branch->code==BNE) new->code=BEQ;
  1187.         code=branch->code;
  1188.             new->typf=out;
  1189.             insert_IC(head->start,new);
  1190.             new=mymalloc(ICS); *new=*cmp;
  1191.             new->change_cnt=new->use_cnt=0;
  1192.             insert_IC(head->start,new);
  1193.             /*  Einsprungpunkte fuer die Modulos.   */
  1194.             for(i=1;i<unroll;i++){
  1195.                 copy_code(start->start->next,cmp->prev,head->start,1);
  1196.                 new=mymalloc(ICS); *new=*branch;
  1197.                 new->change_cnt=new->use_cnt=0;
  1198.                 new->code=LABEL;
  1199.                 new->typf=label+i+1;
  1200.                 insert_IC(head->start,new);
  1201.             }
  1202.             /*  Testen, welches Modulo. */
  1203.             for(i=unroll-2;i>=0;i--){
  1204.                 new=mymalloc(ICS); *new=*branch;
  1205.                 new->change_cnt=new->use_cnt=0;
  1206.                 new->code=BEQ;
  1207.                 if(i>0) new->typf=label+i+1;
  1208.                    else new->typf=start->start->typf;
  1209.                 insert_IC(head->start,new);
  1210.                 new=mymalloc(ICS); *new=*branch;
  1211.                 new->change_cnt=new->use_cnt=0;
  1212.                 if(SWITCHSUBS) new->q1.val.vlong=l2zl(1L);
  1213.                     else       new->q1.val.vlong=l2zl(i);
  1214.                 eval_const(&new->q1.val,LONG);
  1215.                 new->q1.flags=VAR;
  1216.                 new->q1.v=v;
  1217.                 new->q1.val.vlong=l2zl(0L);
  1218.                 new->typf=t->flags;
  1219.                 if(SWITCHSUBS||i==0){
  1220.                     new->code=TEST;
  1221.                     insert_IC(head->start,new);
  1222.                     if(i>0){
  1223.                         new=mymalloc(ICS);
  1224.                         *new=*head->start->next;
  1225.                         new->change_cnt=new->use_cnt=0;
  1226.                         new->code=SUB;
  1227.                         new->z=new->q1;
  1228.                         new->q2.flags=KONST;
  1229.                         insert_const2(&new->q2.val,new->typf&NU);
  1230.                         insert_IC(head->start,new);
  1231.                     }
  1232.                 }else{
  1233.                     new->code=COMPARE;
  1234.                     new->q2.flags=KONST;
  1235.                     insert_const2(&new->q2.val,new->typf&NU);
  1236.                     insert_IC(head->start,new);
  1237.                 }
  1238.             }
  1239.             /*  Durchlaeufe modulo unroll berechnen.    */
  1240.             new=mymalloc(ICS); *new=*branch;
  1241.             new->change_cnt=new->use_cnt=0;
  1242.             new->code=AND;
  1243.             new->typf=t->flags;
  1244.             new->q1.flags=VAR;
  1245.             new->q1.v=v;
  1246.             new->q1.val.vlong=l2zl(0L);
  1247.             new->z=new->q1;
  1248.             new->q2.flags=KONST;
  1249.             new->q2.val.vlong=l2zl(unroll-1);
  1250.             eval_const(&new->q2.val,LONG);
  1251.             insert_const2(&new->q2.val,new->typf);
  1252.             insert_IC(head->start,new);
  1253.             new=mymalloc(ICS);
  1254.         *new=*ind;
  1255.             new->change_cnt=new->use_cnt=0;
  1256.             new->code=DIV;
  1257.             new->q1=head->start->next->z;
  1258.             new->z=new->q1;
  1259.             insert_IC(head->start,new);
  1260.         new=mymalloc(ICS);
  1261.         *new=*head->start->next;
  1262.         new->code=ADD;
  1263.         insert_IC(head->start,new);
  1264.         if(code==BLT||code==BGT){
  1265.           new=mymalloc(ICS);
  1266.           *new=*head->start->next;
  1267.           new->code=SUB;
  1268.           new->q2.val.vlong=l2zl(1L);
  1269.           eval_const(&new->q2.val,LONG);
  1270.           insert_const2(&new->q2.val,new->typf);
  1271.           insert_IC(head->start,new);
  1272.         }
  1273.             new=mymalloc(ICS);
  1274.         *new=*head->start->next;
  1275.             new->change_cnt=new->use_cnt=0;
  1276.             new->code=SUB;
  1277.             if(!compare_objs(&ind->z,&cmp->q1,new->typf)){
  1278.                 if(code==BLT||code==BLE){new->q1=cmp->q2;new->q2=ind->z;}
  1279.                     else                {new->q2=cmp->q2;new->q1=ind->z;}
  1280.             }else{
  1281.                 if(code==BLT||code==BLE){new->q1=cmp->q1;new->q2=ind->z;}
  1282.                     else                {new->q2=cmp->q1;new->q1=ind->z;}
  1283.             }
  1284.         if(ind->code==SUB){
  1285.           struct obj o;
  1286.           o=new->q1;new->q1=new->q2;new->q2=o;
  1287.         }
  1288.             insert_IC(head->start,new);
  1289.             copy_code(start->start->next,cmp->prev,start->start,unroll-1);
  1290.             label+=unroll;
  1291.             changed|=2;
  1292.         }
  1293.         first_ur=m->next;
  1294.         free(m);
  1295.     }
  1296.     return(changed);
  1297. }
  1298. void unroll(struct flowgraph *start,struct flowgraph *head)
  1299. /*  Versucht loop-unrolling.                                            */
  1300. {
  1301.     struct flowlist *lp;struct flowgraph *end,*g;struct IC *p,*m,*branch,*cmp;
  1302.     struct obj *o,*e,*cc; union atyps init_val,end_val,step_val;
  1303.     unsigned char *tmp;
  1304.     long dist,step,ic_cnt,n;
  1305.     int bflag=0,t=0,i,flags=0; /* 1: sub, 2: init_val gefunden  */
  1306.     end=start->loopend;
  1307.     if(DEBUG&1024) printf("checking for possible unrolling from %d to %d\n",start->index,end->index);
  1308.     for(lp=start->in;lp;lp=lp->next)
  1309.         if(lp->graph->index>start->index&&lp->graph->index<=end->index&&lp->graph!=end) return;
  1310.     if(DEBUG&1024) printf("only one backward-branch\n");
  1311.     e=0; p=end->end;
  1312.     do{
  1313.         if(p->code>=BEQ&&p->code<BRA){ branch=p;bflag=p->code;cc=&p->q1; }
  1314.         if(p->code==TEST){
  1315.             if(compare_objs(cc,&p->z,p->typf)) return;
  1316.             o=&p->q1;t=p->typf;cmp=p;
  1317.             end_val.vlong=l2zl(0L); eval_const(&end_val,LONG);
  1318.             insert_const2(&end_val,t);
  1319.             break;
  1320.         }
  1321.         if(p->code==COMPARE){
  1322.             if(compare_objs(cc,&p->z,p->typf)) return;
  1323.             cmp=p;
  1324.             if(p->q1.flags&VAR){
  1325.                 if(ind_vars[p->q1.v->index]){
  1326.                     o=&p->q1;t=p->typf;
  1327.                     e=&p->q2;
  1328.                     break;
  1329.                 }
  1330.             }
  1331.             if(p->q2.flags&VAR){
  1332.                 if(ind_vars[p->q2.v->index]){
  1333.                     o=&p->q2;t=p->typf;
  1334.                     e=&p->q1;
  1335.                     if(bflag==BLT) bflag=BGT;
  1336.                     if(bflag==BLE) bflag=BGE;
  1337.                     if(bflag==BGT) bflag=BLT;
  1338.                     if(bflag==BGE) bflag=BLE;
  1339.                     break;
  1340.                 }
  1341.             }
  1342.             return;
  1343.         }
  1344.         if(p==end->start) return;
  1345.         p=p->prev;
  1346.     }while(p);
  1347.     if(!e||(e->flags&KONST)){
  1348.         if(e) end_val=e->val;
  1349.         if(DEBUG&1024) printf("end condition is constant\n");
  1350.     }else{
  1351.         if(!(e->flags&VAR)) return;
  1352.         i=e->v->index;
  1353.         if(e->flags&DREFOBJ) i+=vcount-rcount;
  1354.         if(DEBUG&1024) printf("testing end-condition\n");
  1355.         memcpy(rd_defs,end->rd_in,dsize);
  1356.         for(m=end->start;m;m=m->next){
  1357.             if(m==cmp){
  1358.                 if(DEBUG&1024) pric2(stdout,m);
  1359.                 if(!def_invariant(i,-1)) return;
  1360.                 if(DEBUG&1024) printf("end condition loop-invariant\n");
  1361.                 break;
  1362.             }
  1363.             rd_change(m);
  1364.             if(m==end->end) ierror(0);
  1365.         }
  1366.     }
  1367.     p=ind_vars[o->v->index];
  1368.     if(!p) return;
  1369.     if(compare_objs(o,&p->z,t)) return;
  1370.     if(DEBUG&1024) printf("loop condition only dependant on induction var\n");
  1371.     if(!(p->q2.flags&KONST)) return;
  1372.     if(DEBUG&1024) printf("induction is constant\n");
  1373.     for(ic_cnt=0,g=start;g;g=g->normalout){
  1374.         for(m=g->start;m;m=m->next){
  1375.             if(m==p&&!always_reached(start,end,g,p,1)) return;
  1376.             ic_cnt++;
  1377.             if(m==g->end) break;
  1378.         }
  1379.         if(g==end) break;
  1380.     }
  1381.     ic_cnt-=2;  /*  Branch und Test */
  1382.     if(DEBUG&1024) printf("induction always reached\n");
  1383.     if(DEBUG&1024) printf("ICs in loop: %ld\n",ic_cnt);
  1384.     step_val=p->q2.val;
  1385.     if(p->code==SUB) flags|=1;
  1386.     if(e&&!(e->flags&KONST)){
  1387.         /*  Anzahl der Schleifendurchlaeufe kann beim Eintritt in die   */
  1388.         /*  Schleife zur Laufzeit berechnet werden.                     */
  1389. /*         add_ur(UNROLL_INVARIANT,0,4,start,head,cmp,branch,p); */
  1390.         return;
  1391.     }
  1392.     i=p->z.v->index;
  1393.     if(p->z.flags&DREFOBJ) i+=vcount-rcount;
  1394.     tmp=mymalloc(dsize);
  1395.     memcpy(tmp,head->rd_out,dsize);
  1396.     if(BTST(tmp,i+dcount+1)) return; /*  keine eind. Def.    */
  1397.     bvintersect(tmp,defs[i],dsize);
  1398.     for(i=1;i<=dcount;i++){
  1399.         if(BTST(tmp,i)){
  1400.             if(DEBUG&1024){ printf("possible init:\n");pric2(stdout,dlist[i]);}
  1401.             if((flags&2)||dlist[i]->code!=ASSIGN||!(dlist[i]->q1.flags&KONST)){
  1402.                 free(tmp);return;
  1403.             }
  1404.             init_val=dlist[i]->q1.val;
  1405.             flags|=2;
  1406.         }
  1407.     }
  1408.     free(tmp);
  1409.     if(!(flags&2)) return;
  1410.     if(DEBUG&1024){
  1411.         printf("loop number determinable\n");
  1412.         printf("init_val: ");printval(stdout,&init_val,t,1);
  1413.         printf("\nend_val: ");printval(stdout,&end_val,t,1);
  1414.         printf("\nstep_val: ");printval(stdout,&step_val,t,1);
  1415.         printf("\nflags=%d bflag=%d\n",flags,bflag);
  1416.     }
  1417.     /*  Nur integers als Induktionsvariablen.   */
  1418.     if((t&NQ)>LONG) return;
  1419.     /*  Distanz und Step werden als long behandelt, deshalb pruefen, ob */
  1420.     /*  alles im Bereich des garantierten Mindestwerte fuer long.       */
  1421.     /*  Wenn man hier die Arithmetik der Zielmaschine benutzen wuerde,  */
  1422.     /*  koennte man theoretisch mehr Faelle erkennen, aber das waere    */
  1423.     /*  recht popelig und man muss sehr aufpassen.                      */
  1424.     if(t&UNSIGNED){
  1425.         eval_const(&end_val,t);
  1426.         if(!zulleq(vulong,l2zl(2147483647))) return;
  1427.         dist=zul2ul(vulong);
  1428.         eval_const(&init_val,t);
  1429.         if(!zulleq(vulong,l2zl(2147483647))) return;
  1430.         dist-=zul2ul(vulong);
  1431.         eval_const(&step_val,t);
  1432.         if(!zulleq(vulong,l2zl(2147483647))) return;
  1433.         step=zul2ul(vulong);
  1434.     }else{
  1435.         eval_const(&end_val,t);
  1436.         if(!zlleq(vlong,l2zl(2147483647/2))) return;
  1437.         if(zlleq(vlong,l2zl(-2147483647/2))) return; /*  eins weniger als moeglich waere */
  1438.         dist=zl2l(vlong);
  1439.         eval_const(&init_val,t);
  1440.         if(!zlleq(vlong,l2zl(2147483647/2))) return;
  1441.         if(zlleq(vlong,l2zl(-2147483647/2))) return; /*  eins weniger als moeglich waere */
  1442.         dist-=zl2l(vlong);
  1443.         eval_const(&step_val,t);
  1444.         if(!zlleq(vlong,l2zl(2147483647))) return;
  1445.         if(zlleq(vlong,l2zl(-2147483647))) return; /*  eins weniger als moeglich waere */
  1446.         step=zl2l(vlong);
  1447.     }
  1448.     if(flags&1) step=-step;
  1449.     if(DEBUG&1024) printf("dist=%ld, step=%ld\n",dist,step);
  1450.     if(step==0) ierror(0);
  1451.     /*  Die Faelle kann man noch genauer untersuchen, ob die Schleife   */
  1452.     /*  evtl. nur einmal durchlaufen wird o.ae.                         */
  1453.     if(step<0&&dist>=0){
  1454.         if(report_suspicious_loops){ error(208);report_suspicious_loops=0;}
  1455.         return;
  1456.     }
  1457.     if(step>0&&dist<=0){
  1458.         if(report_suspicious_loops){ error(208);report_suspicious_loops=0;}
  1459.         return;
  1460.     }
  1461.     if(bflag==BEQ){
  1462.         if(report_suspicious_loops){ error(208);report_suspicious_loops=0;}
  1463.         return;
  1464.     }
  1465.     /*  Aufpassen, ob das Schleifenende bei BNE auch getroffen wird.    */
  1466.     if(bflag==BNE){
  1467.         if(dist%step){
  1468.             if(report_suspicious_loops){ error(208);report_suspicious_loops=0;}
  1469.             return;
  1470.         }
  1471.     }
  1472.     if(bflag==BLT||bflag==BGT||bflag==BNE){
  1473.         if(step>0) dist--; else dist++;
  1474.     }
  1475.     if(dist/step<0) ierror(0);
  1476.     if(DEBUG&1024) printf("loop is executed %ld times\n",dist/step+1);
  1477.     if(start->start->code!=LABEL) ierror(0);
  1478.     if(ic_cnt*(dist/step+1)<=unroll_size){
  1479.         /*  Schleife komplett ausrollen.    */
  1480.         add_ur(UNROLL_COMPLETELY,dist/step+1,dist/step+1,start,head,cmp,branch,p);
  1481.     }else{
  1482.         /*  Schleife teilweise ausrollen.   */
  1483.         n=(unroll_size-ic_cnt-2)/(2*ic_cnt);
  1484.         add_ur(UNROLL_MODULO,dist/step+1,n,start,head,cmp,branch,p);
  1485.     }
  1486. }
  1487.  
  1488. int loop_optimizations(struct flowgraph *fg)
  1489. /*  steuert Optimierungen in Schleifen  */
  1490. {
  1491.     int changed=0,i;
  1492.     struct flowgraph *g,*last;
  1493.     if(DEBUG&1024) print_flowgraph(fg);
  1494.     if(loops(fg,0)==0) return(0);
  1495.     if(DEBUG&1024) print_flowgraph(fg);
  1496.     first_fg=fg=create_loop_headers(fg,0);
  1497.     if(DEBUG&1024) print_flowgraph(fg);
  1498.     num_defs();
  1499.  
  1500.     bsize=(basic_blocks+CHAR_BIT)/CHAR_BIT;
  1501.     fg_tmp=mymalloc(bsize);
  1502.     ind_vars=mymalloc(vcount*sizeof(*ind_vars));
  1503.     invariant=mymalloc(dsize);
  1504.     inloop=mymalloc(dsize);
  1505.     rd_defs=mymalloc(dsize);
  1506.     rd_tmp=mymalloc(dsize);
  1507.     rd_mode=1;
  1508.     reaching_definitions(fg);
  1509.     if(DEBUG&1024) print_flowgraph(fg);
  1510.     moved=mymalloc(dsize);
  1511.     memset(moved,0,dsize);
  1512.     moved_completely=mymalloc(dsize);
  1513.     memset(moved_completely,0,dsize);
  1514.     not_movable=mymalloc(dsize);
  1515.  
  1516.     first_mov=last_mov=0;
  1517.     first_sr=last_sr=0;
  1518.  
  1519.     for(last=0,g=fg;g;g=g->normalout){
  1520.         if(g->loopend){
  1521.             frequency_reduction(g,g->loopend,last);
  1522.             strength_reduction(g,g->loopend,last); 
  1523.             if(optflags&2048) unroll(g,last);
  1524.         }
  1525.         last=g;
  1526.     }
  1527.  
  1528.     for(i=0;i<vcount;i++) free(defs[i]);
  1529.     free(defs);
  1530.     free(dlist);
  1531.     free(rd_globals);
  1532.     free(rd_statics);
  1533.     free(rd_address);
  1534.     free(rd_drefs);
  1535.     free(rd_parms);
  1536.     free(rd_defs);
  1537.     free(rd_tmp);
  1538.     free(rd_vars);
  1539.     free(invariant);
  1540.     free(inloop);
  1541.     changed|=move_to_head();
  1542.     if(DEBUG&1024) puts("done");
  1543.     changed|=do_sr();
  1544.     if(DEBUG&1024) puts("done");
  1545.     changed|=do_unroll(changed);
  1546.     if(DEBUG&1024) puts("done");
  1547.     free(moved);
  1548.     free(not_movable);
  1549.     free(moved_completely);
  1550.     if(DEBUG&1024) puts("4");
  1551.     if(changed&2){
  1552.         if(DEBUG&1024) printf("must repeat num_vars\n");
  1553.         free(vilist);
  1554.         free(av_globals);free(av_statics);
  1555.         free(av_drefs);free(av_address);
  1556.         num_vars();
  1557.     }
  1558.  
  1559.     free(ind_vars);
  1560.     free(fg_tmp);
  1561.  
  1562.     return(changed);
  1563. }
  1564.  
  1565.